Prof.  Gregory  Gutin
Royal Holloway University of London,  UK

Title: Complexity Dichotomies for Maximum Weighted Digraph Partition Problem

Abstract:

We'll discuss complexity dichotomies (P vs NP) proved for a recently introduced problem Maximum Weighted Digraph Partition (MWDP), which generalizes Maximum Weight Directed Cut and a number of other optimization problems on directed and undirected graphs, see [1,2,3]. The dichotomies have applications in graph theory, game theory and economics. While the original proofs were purely graph-theoretical, now we can prove most of them using dichotomies for the Valued Constraint Satisfaction Problem.
Joint work with A. Deligkas, E. Eiben, G. Gutin, P.R. Neary, G. Osipov, M. Wahlstrom and A. Yeo.
[1] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems, Proc. IJCAI 2023
[2] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem, arXiv:2307.01109.
[3] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Some coordination problems are harder than others, arXiv:2311.03195. 

Biography:

Prof Gregory Gutin received his PhD in Mathematics in 1993 from Tel Aviv University under the supervision of Noga Alon. Since September 2000 Gutin has been Professor in Computer Science at Royal Holloway, University of London. Gutin's research interests are in graph theory and combinatorial optimization, algorithms and complexity, game theory and information security. He has over 270 papers published or accepted for publication in refereed journals and conference proceedings. In particular, he co-authored with Joergen Bang-Jensen two editions of a monograph Digraphs: Theory, Algorithms and Applications. Gutin was the recipient of the Royal Society Wolfson Research Merit Award in 2014, and the best paper awards at ACM Symposium on Access Control Models and Technologies (SACMAT) 2015, 2016, 2021 and 2022. In 2017 Gutin became a member of Academia Europaea. In 2021 he was elected Fellow of AAIA (Asia-Pacific Artificial Intelligence Association).